package com.zjw.algorithm.ready1;

import com.zjw.algorithm.utils.TreeNode;

import java.util.*;

public class _二叉树的垂直遍历 {


    public List<List<Integer>> verticalTraversal(TreeNode root) {

        List<int[]> records = new ArrayList<>();
        dfs(root, 0, 0, records);

        records.sort((o1, o2) -> {
            if (o1[0] != o2[0]) {
                return o1[0] - o2[0];
            }

            if (o1[1] != o2[1]) {
                return o1[1] - o2[1];
            }
            return o1[2] - o2[2];
        });

        int leftIndexJust = records.get(0)[0];

        List<List<Integer>> result = new ArrayList<>();
        for (int[] record : records) {
            int col = record[0];
            int index = col - leftIndexJust;
            if (result.size() > index) {
                result.get(index).add(record[2]);
            } else {
                ArrayList<Integer> list = new ArrayList<>();
                result.add(list);
                list.add(record[2]);
            }
        }

        return result;
    }

    private void dfs(TreeNode root, int cow, int row, List<int[]> records) {
        if (root == null) {
            return;
        }
        records.add(new int[]{cow, row, root.val});
        dfs(root.left, cow - 1, row + 1, records);
        dfs(root.right, cow + 1, row + 1, records);
    }

}
